package com.wangjie.datastructuredesign;

import java.util.HashMap;
import java.util.Map;

/**
 * @author jieshao
 * @date 2022/5/20 11:08
 *
 * 146. LRU 缓存(请你设计并实现一个满足 LRU 缓存约束的数据结构，函数 get 和 put 必须以 O(1) 的平均时间复杂度运行)
 *
 * 思路：要让 get 和 put 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件
 *
 * 1. 显然 cache 中的元素必须有时序，以区分最近使用和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置
 * 2. 我们要在 cache 中快速查找某个 key 是否已存在并得到对应的 val
 * 3. 每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素
 *
 * 那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序，链表有顺序之分，插入删除快，但是查找慢，所以结合一下，
 * 形成一种新的数据结构叫做哈希链表(LinkedHashMap)，LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体
 */
public class LRUCache {
    // key -> Node(key, val)
    private Map<Integer, Node> map;

    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;

    // 最大容量
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    /**
     * 由于我们要同时维护一个双链表 cache 和一个哈希表 map，很容易漏掉一些操作，比如说删除某个 key 时，在 cache 中
     * 删除了对应的 Node，但是却忘记在 map 中删除key，解决这种问题的有效方法是在这两种数据结构之上提供一层抽象 API，
     * 尽量让 get 和 put 方法避免直接操作 map 和 cache 的细节
     */

    /**
     * 将某个 key 提升为最近使用的
     *
     * @param key
     */
    private void makeRecently(int key) {
        Node node = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(node);
        // 重新插入到链表尾部
        cache.addLast(node);
    }

    /**
     * 添加最近使用的元素
     *
     * @param key
     * @param val
     */
    private void addRecently(int key, int val) {
        Node node = new Node(key, val);
        // 链表尾部就是最近使用的元素
        cache.addLast(node);
        // 在 map 中添加 key 的映射
        map.put(key, node);
    }

    /**
     * 删除某一个 key
     *
     * @param key
     */
    private void deleteKey(int key) {
        Node node = map.get(key);
        // 从链表中删除
        cache.remove(node);
        // 从 map 中删除
        map.remove(key);
    }

    /**
     * 删除最久未使用的元素
     */
    private void removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node node = cache.removeFirst();
        // 从 map 中删除它的 key
        map.remove(node.key);
    }

    /**
     * 如果 key 存在于缓存中，返回 key 对应的值，否则返回 -1
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将 key 提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }

    /**
     * 如果 key 存在于缓存中，修改 key 对应的 val，并将 key 提升为最近使用的
     * 如果 key 不存在缓存中，若容量已满，淘汰最久未使用的 key，插入 key 和 val 为最近使用的数据
     *
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }
        if (capacity == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }
}